#!/usr/bin/env python
# -*- coding: utf-8 -*-
# @Time    : 2020/8/22 14:40
# @USER    : Shengji He
# @File    : 24Game.py
# @Software: PyCharm
# @Version  : Python-
# @TASK:
from typing import List


class Solution:
    def judgePoint24(self, nums: List[int]) -> bool:
        """
        You have 4 cards each containing a number from 1 to 9. You need to judge whether they could operated
        through *, /, +, -, (, ) to get the value of 24.

        Example 1:
            Input: [4, 1, 8, 7]
            Output: True
            Explanation: (8-4) * (7-1) = 24
        Example 2:
            Input: [1, 2, 1, 2]
            Output: False
        Note:
            - The division operator / represents real division, not integer division. For example, 4 / (1 - 2/3) = 12.
            - Every operation done is between two numbers. In particular, we cannot use - as a unary operator. For example, with [1, 1, 1, 1] as input, the expression -1 - 1 - 1 - 1 is not allowed.
            - You cannot concatenate numbers together. For example, if the input is [1, 2, 1, 2], we cannot write this as 12 + 12.

        :param nums:
        :return:
        """
        TARGET = 24
        EPSILON = 1e-6
        ADD, MULTIPLY, SUBTRACT, DIVIDE = 0, 1, 2, 3

        def solve(nums: List[float]) -> bool:
            if not nums:
                return False
            if len(nums) == 1:
                return abs(nums[0] - TARGET) < EPSILON

            for i, x in enumerate(nums):
                for j, y in enumerate(nums):
                    if i != j:
                        newNums = list()
                        for k, z in enumerate(nums):
                            if k != i and k != j:
                                newNums.append(z)
                        for k in range(4):
                            if k < 2 and i > j:
                                continue
                            if k == ADD:
                                newNums.append(x + y)
                            elif k == MULTIPLY:
                                newNums.append(x * y)
                            elif k == SUBTRACT:
                                newNums.append(x - y)
                            elif k == DIVIDE:
                                if abs(y) < EPSILON:
                                    continue
                                newNums.append(x / y)
                            if solve(newNums):
                                return True
                            newNums.pop()
            return False

        return solve(nums)


if __name__ == '__main__':
    S = Solution()
    nums = [4, 1, 8, 7]
    print(S.judgePoint24(nums))
    print('done')
